package 中等.动态规划.子序列;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindromic-substring/
 */
public class 最长回文子串_5 {

    public static void main(String[] args) {

        System.out.println(longestPalindrome("bananas"));

    }


    /**
     * 动态规划
     * 1，子问题：
     * 以 i 开头，j 结尾的子串是否是回文字串
     * 2，状态转移方程：
     * 如果 [i,j] 是回文字串，且 s[i-1] == s[j+1]
     * 那么 [i-1,j+1] 也是回文字串
     * 分类讨论：
     * [i,j] 超过 2 个字符
     * dp[i][j] = dp[i+1][j-1] & s[i] == s[j]
     * i==j 一个字符，一定是回文字串
     * i+1==j 两个字符，判断 s[i] == s[j]
     * <p>
     * 注意：如果 j < i 不合法的，排除掉
     */
    public static String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        int l = 0, r = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (j < i) continue;

                if (i == j) {  // 只有一个字符
                    dp[i][j] = true;
                } else if (j - i == 1) {  // 只有两个字符
                    if (chars[i] == chars[j]) {
                        dp[i][j] = true;
                    }
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && chars[i] == chars[j];
                }

                if (dp[i][j] && j - i > r - l) {
                    l = i;
                    r = j;
                }
            }
        }
        return s.substring(l, r + 1);
    }

}
